/**
 * 二叉搜索树
 */
;(function(window){
	var Node = function(data){
		return {
			data: data,
			lNode: null,
			rNode: null
		};
	};

	var BinarySearchTree = function(){
		this._root = null;
	};
	BinarySearchTree.prototype = {
		constructor: BinarySearchTree,
		getNode: function(key){
			if( this._root == null ) return null;
			var node = this._root;
			while( node.data != key ){
				if( key > node.data ) node = node.rNode;
				if( key < node.data ) node = node.lNode;
				if( node == null ) return null;
			}
			return node;
		},
		getMinimum: function(){
			var node = this._root;
			if( node == null ) return null;
			while( node.lNode )
				node = node.lNode;
			return node;
		},
		getMaximum: function(){
			var node = this._root;
			if( node == null ) return null;
			while( node.rNode )
				node = node.rNode;
			return node;
		},
		insert: function(data){
			var newNode = Node(data);
			if(this._root == null){
				this._root = newNode;
				return;
			}
			var node = this._root;
			while( true ){
				// 遇到重复关键字放右子节点
				if( data >= node.data ){
					if( node.rNode == null ){ node.rNode = newNode; return;}
					else node = node.rNode;
				}else{
					if( node.lNode == null ){ node.lNode = newNode; return; }
					else node = node.lNode;
				}
			}
		},
		deleteNode: function(key){
			if( this._root == null ) return null;
			var node = this._root, parentNode = node, child;
			while( node.data != key ){
				parentNode = node;
				if( key > node.data ) { node = node.rNode; child = 'rNode'; }
				if( key < node.data ) { node = node.lNode; child = 'lNode'; }
				if( node == null ) return null;
			}
			if( node.lNode == null && node.rNode == null ){
				// 如果找到的是叶子节点
				if( node == this._root ) // 如果找到的叶子节点是根节点
					this._root = null;
				else // 如果不是根节点
					parentNode[child] = null;
			}else if( node.lNode == null ){
				// 有左子节点但没有右子结点的情况
				if( node == this._root )
					this._root = null;
				else
					parentNode[child] = node.rNode;
			}else if( node.rNode == null ){
				// 有右子节点但没有左子节点的情况
				if( node == this._root )
					this._root = null;
				else
					parentNode[child] = node.lNode;
			}else{
				// 有两个子节点的情况
				var sParentNode = node,sNode = node.rNode;
				while( sNode.lNode != null ){
					sParentNode = sNode;
					sNode = sNode.lNode;
				}
				if( sParentNode == node ){
					// 被删除节点右子节点没有左子节点
					sNode.lNode = node.lNode;
					parentNode[child] = sNode;
				}else{
					sParentNode.lNode = sNode.rNode;
					sNode.lNode = node.lNode;
					sNode.rNode = node.rNode;
					parentNode[child] = sNode;
				}
			}
			return node;
		},
		inorderTraveral: function(node, callback, result){
			if( arguments.length == 1 ) {
				result = [];
				callback = node;
				node = this._root;
			}
			if( node != null ){
				this.inorderTraveral(node.lNode, callback, result);
				callback(node);result.push(node.data);
				this.inorderTraveral(node.rNode, callback, result);
			}
			return result;
		},
		preorderTraveral: function(node, callback){
			if( arguments.length == 1 ) {
				callback = node;
				node = this._root;
			}
			if( node != null ){
				callback(node);
				this.preorderTraveral(node.lNode, callback);
				this.preorderTraveral(node.rNode, callback);
			}
		},
		postorderTraveral: function(node, callback){
			if( arguments.length == 1 ) {
				callback = node;
				node = this._root;
			}
			if( node != null ){
				this.postorderTraveral(node.lNode, callback);
				this.postorderTraveral(node.rNode, callback);
				callback(node);
			}
		}
	};
	window.BinarySearchTree = BinarySearchTree;
})(window);